package LeetCode.month02.day59;

public class No990 {
    int[] parent = new int[26];
    public boolean equationsPossible(String[] equations) {
        int n = equations.length;
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            String s = equations[i];
            if(s.charAt(1)=='='){
                int index1 = s.charAt(0)-'a';
                int index2 = s.charAt(3)-'a';
                union(index1,index2);
            }
        }

        for (int i = 0; i < n; i++) {
            String s = equations[i];
            if(s.charAt(1)=='!'){
                int index1 = s.charAt(0)-'a';
                int index2 = s.charAt(3)-'a';
                if(find(index1)==find(index2)) return false;
            }
        }
        return true;
    }

    public void union(int index1,int index2){
        parent[find(index1)] = find(index2);
    }
    public int find(int index){
        while(parent[index]!=index){
            parent[index]=parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
}